package net.xuele.learn.dancing.dp;

import java.util.Arrays;

/**
 * 表达式的转换
 * dp[n] = dp[n-1]+dp[n-2]+dp[n-5]
 * 转换为dp[n] = dp[n] + dp[n-i] i={1,2,5}
 * dp数组的作用是用来记录子问题的，或者说是消除子问题的
 * 子问题：子问题可以直接使用啊！！！！自底向上求解的时候，子问题就是已有的结论，可以直接使用
 */
public class CoinChange {

    public int coinChange(int[] coins, int amount) {
        // 数组dp[n]表示当前的目标金额是n，至少需要dp(n)个硬币凑出该金额
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        // base case
        dp[0] = 0;
        // 外层 for 循环在遍历所有状态的所有取值
        for (int i = 0; i < dp.length; i++) {
            // 内层 for 循环在求所有选择的最小值
            for (int coin : coins) {
                // 子问题无解，跳过
                if (i - coin < 0) continue;
                // dp[i]的原值是1，存在一枚硬币就能凑齐的情况
                // 需要知道dp[n]需要多少枚硬币凑齐，只需要知道dp[n-coin]需要多少枚硬币，
                // +1是加上面额为coin的这枚硬币了
                // 打个比方，比如需要知道凑齐8元最少需要多少枚硬币，可选的硬币是1、2、5，则需要看的子问题是
                // dp[7]、dp[6]、dp[3]（对应的+1则是分别加上1元、2元、5元面额；对于dp[7]、dp[6]、dp[3]而言，
                // 又需要去看待其子问题），但是在当前这个时间节点上，我们是已经求得了dp[7]、dp[6]、dp[3]的，因为他们是dp[8]的
                // 子问题
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = new int[]{1, 2, 5};
        int amount = 11;
        CoinChange coinChange = new CoinChange();
        int[] a = new int[]{7, 6, 4, 3, 1};
        System.out.println(coinChange.maxProfit(a));
    }


    /**
     * 先买入再卖出
     * <p>
     * dp数组表示第i天卖出的收益
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {

        int length = prices.length;
        if (length == 0) return 0;

        int dp_0 = 0;
        int dp_1 = Integer.MIN_VALUE;

        for (int i = 0; i < length; i++) {
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            dp_1 = Math.max(dp_1, -prices[i]);
        }


        return dp_0;

        // 这是一个穷举的过程
//        int max = 0;
//        for (int i = 0; i < prices.length - 1; i++) {
//            int buy = prices[i];
//            for (int j = i + 1; j < prices.length; j++) {
//                int sell = prices[j];
//                if (buy < sell) {
//                    max = Math.max(max, sell - buy);
//                }
//            }
//        }
//        return max;
    }

    /**
     * 多次交易一只股票
     *
     * @param prices
     * @return
     */
    public int maxProfit2(int[] prices) {
        int n = prices.length;
        // dp[i][0] 表示第i天交易完后手里没有股票的最大利润
        // dp[i][1] 表示第i天交易完后手里持有一支股票的最大利润
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];


//            int n = prices.length;
//            int dp0 = 0, dp1 = -prices[0];
//            for (int i = 1; i < n; ++i) {
//                dp0 = Math.max(dp0, dp1 + prices[i]);
//                dp1 = Math.max(dp1, dp0 - prices[i]);
//            }
//            return dp0;


    }

    /**
     * @param max_k  交易次数
     * @param prices
     * @return
     */
    public int maxProfit3(int max_k, int[] prices) {
        // 一次交易由买入和卖出构成，至少需要两天。
        // 所以说有效的限制k应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity
        int n = prices.length;
        if (max_k > n / 2) {
            return maxProfit2(prices);
        }
        // dp[i][k][0] 表示第i天交易完后手里没有股票的最大利润
        // dp[i][k][1] 表示第i天交易完后手里持有一支股票的最大利润
        int[][][] dp = new int[n][max_k + 1][2];

        for (int i = 0; i < n; ++i) {
            for (int k = max_k; k >= 1; k--) {
                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        }
        return dp[n - 1][max_k][0];


    }
}
